package com.zk.algorithm.array;

/**
 * 统计逆序对
 * 来自极客时间
 *
 * https://time.geekbang.org/column/article/73503
 */
public class CountReversePairs {

    private int num = 0; // 全局变量或者成员变量

    public int count(int[] a, int n) {
        num = 0;
        mergeSortCounting(a, 0, n - 1);
        return num;
    }

    private void mergeSortCounting(int[] a, int p, int r) {
        if (p >= r) return;

        int q = (p + r) / 2;
        mergeSortCounting(a, p, q);
        mergeSortCounting(a, q + 1, r);
        merge(a, p, q, r);
    }

    private void merge(int[] a, int left /** 左边 **/, int middle /** 中间 **/, int right /** 右边 **/) {
        int i = left, j = middle + 1, k = 0;
        int[] tmp = new int[right - left + 1];

        while (i <= middle && j <= right) {
            if (a[i] <= a[j]) {
                tmp[k++] = a[i++];
            } else {
                num += (middle - i + 1); // 统计 left - middle 之间，比 a[j] 大的元素个数
                tmp[k++] = a[j++];
            }
        }

        while (i <= middle) { // 处理剩下的
            tmp[k++] = a[i++];
        }

        while (j <= right) { // 处理剩下的
            tmp[k++] = a[j++];
        }

        for (i = 0; i <= right - left; ++i) { // 从 tmp 拷贝回 a
            a[left + i] = tmp[i];
        }
    }

}